von Neumann's minimax theorem

Theorem

In any matrix game $A$, the average security levels of the players in mixed strategies coincide, that is,

This is known as the value of the game.

Corollary

#incomplete

Theorem (von Neumann, 1928)

Every two-player zero-sum game in which a player has a finite number of pure strategies has a value in mixed strategies.

Note

The value is also known as saddle-point equilibrium, so every finite zero-sum matrix game has a saddle point equilibrium in mixed strategies.

There is a connection noted by von Neumann to topology, wherefore the "immediate reason for this is the occurrence of a certain "minimum-maximum" problem, familiar from the calculus of variations." (von Neumann 1945)

finite two-player zero-sum extensive-form game

Every finite two-player zero-sum extensive-form game with perfect information has a value.

See also

• minimax solution, minimax strategies
• minmax strategy, maxmin strategy
• Sion's minimax theorem (a generalization of von Neumann's minimax theorem)
• Yao's lemma, an application to randomized algorithms

References

1. M. Maschler, E. Solan, and Shmuel Zamir, Game Theory, Cambridge University Press, 2013, pp. 27-28, 151.
2. https://mathworld.wolfram.com/MinimaxTheorem.html
3. https://en.wikipedia.org/wiki/Minimax_theorem
4. v. Neumann, J. (1928). Zur theorie der gesellschaftsspiele. Mathematische annalen, 100(1), 295-320. https://doi.org/10.1007/BF01448847
5. v. Neumann, J. (1945). A model of general economic equilibrium. The Review of Economic Studies, 13(1), 1-9. https://doi.org/10.2307/2296111
   • original: Neumann, V. (1937). Über ein ökonomsiches Gleichungssystem und eine Verallgemeinering des Brouwerschen Fixpunktsatzes. In Erge. Math. Kolloq. (Vol. 8, pp. 73-83).